#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<limits.h>
#include<stdbool.h>

 struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    
};

int minDepth(struct TreeNode* root) {
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    int min_Depth = INT_MAX;
    if (root->left)
        min_Depth = fmin(minDepth(root->left), min_Depth);
    if (root->right)
        min_Depth = fmin(minDepth(root->right), min_Depth);
    return min_Depth + 1;
}

int mySqrt(int x) {
    /*if (x == 0)
        return 0;
    int ans = exp(0.5 * log(x));
    return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);*/
    int l = 0;
    int r = x;
    int ans = 0;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        if ((long long)mid * mid <= x)
        {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return ans;
}

int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; i++)
    {
        p = q;
        q = r;
        r = q + p;
    }
    return r;
}


struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL)
        return head;
    struct ListNode* pcur = head;
    while (pcur->next)
    {
        if (pcur->val == pcur->next->val)
        {
            struct ListNode* next = pcur->next;
            pcur->next = pcur->next->next;
            free(next);
        }
        else
            pcur = pcur->next;
    }
    return head;
}

void inorder(struct TreeNode* root, int* res, int* returnSize)
{
    if (root == NULL)
        return;
    inorder(root->left, res, returnSize);
    res[(*returnSize)++] = root->val;
    inorder(root->right, res, returnSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}

int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
    int** ret = malloc(sizeof(int*) * numRows);
    *returnSize = numRows;
    *returnColumnSizes = malloc(sizeof(int) * numRows);
    for (int i = 0; i < numRows; i++)
    {
        ret[i] = malloc(sizeof(int) * (i + 1));
        (*returnColumnSizes)[i] = i + 1;
        ret[i][0] = ret[i][i] = 1;
        for (int j = 1; j < i; j++)
            ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
    }
    return ret;
}

bool hasPathSum(struct TreeNode* root, int targetSum) {
    if (root == NULL)
        return false;
    if (root->left == NULL && root->right == NULL)
        return targetSum == root->val;
    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}